#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

void reverse(ListNode *head, ListNode *tail)
{
    ListNode *pre = NULL, *cur = head, *next;

    while(cur != tail) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
}

ListNode *reverseKGroup(ListNode *head, int k) 
{
    ListNode dummy(0);
    ListNode *preEnd = &dummy, *curStart = head, *curEnd, *nextStart;
    dummy.next = head;
    
    while (1) {
        curEnd = curStart;
        for (int i = 0; i < k-1 && curEnd; i++)
            curEnd = curEnd->next;
        if (!curEnd) break;

        nextStart = curEnd->next;
        reverse(curStart, nextStart);
        preEnd->next = curEnd;
        curStart->next = nextStart;
        preEnd = curStart;
        curStart = nextStart;
    }
    return dummy.next;
}

ListNode *newList(int data[], int index, int size)
{
    ListNode *node = NULL;
    if (index == size)
        return node;

    node = new ListNode(data[index]);
    node->next = newList(data, index+1, size);
    return node;
}

//test on 1337 online judge and pass all the test
int main(int argc, char **argv)
{

    cout << "-----------------Test 1--------------------" << endl;
    vector<ListNode *> myList;
    int data[] = {1,2,3,4,5,6,7,8,9};
    ListNode *list1, *list2;
    list1 = newList(data, 0, sizeof(data)/sizeof(int));
    list2 = reverseKGroup(list1, 4);
    while(list2) {
        cout << list2->val << " ";
        list2 = list2->next;
    }
    cout << endl;

    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
